1. Field of the Invention
The present invention relates to memory mapping and more particularly to link and mapping pointers in a memory overlay system for maintaining order in reference sequences.
2. Description of the Prior Art
In many data processing applications the technique of expanding memory has been utilized in order to bring up strings of related data or programs from a slow and large bulk storage system to a higher rate accelerator store. One such technique of memory overlay has been described in an application Ser. No. 769,611, entitled "Memory Control Processor," now U.S. Pat. No. 4,080,651, issued on Mar. 21, 1978, assigned to the same assignee and filed concurrently herewith. In this overlay technique most addressing of memory is made by way of the coordinates of the main system and only in the event that that field or segment of main store is already overlayed into the accelerator store is the transformation of address made to the accelerator memory coordinate system. As is commonly recognized in the art the size of an accelerator store is typically cost limited and any overlay thereto is often performed according to some statistically optimized order. Thus in the aforementioned application the overlay occurs into least recently used segments of the accelerator memory. For purposes of organization the segments of accelerator memory are sized to correspond to the segment size of the main or bulk memory. In cases of disc this becomes a sector field which is commonly referred to herein as a memory page. Each page, in turn, includes a plurality of data words which depending on packing density and word size can be of any number. The same considerations supporting the least recently used page overlay technique also dictate that overlay occur in page sequences where related data stretches over more than one page. Similarly, destruction of data in the accelerator memory, referred to herein as the page buffer store, also often entails page strings or links, particularly where one page is of little utility without the associated other pages.
It is therefore the intent and purpose of the present invention to provide a system of pointers which both transforms the main memory referenced address into the corresponding page buffer store address and concurrently invokes the required linking sequences. SUMMARY OF THE INVENTION
Accordingly it is the general purpose and object of the present invention to provide an address transformation system from a main memory referenced address system to a temporary or volatile accelerator memory system.
Other objects of the invention are to provide for logical linking of memory overlays which depend both on the linking of the overlayed and overlaying store.
Yet further objects of the invention are to provide a pointer and link mapping arrangement for use with a least recently used memory overlay technique or any other logical algorithm based on page usage history.
Briefly these and other objects are accomplished within the present invention by combining a least recently used memory overlay system, described at length in a concurrently filed application, Ser. No. 769,611, now U.S. Pat. No. 4,080,651, entitled "Memory Control Processor" and appended herein as Appendix A, with a map system which includes a pointer to the corresponding segment in the accelerator memory (or page buffer store) a status bit indicating if this segment or page is in the page buffer store, a page link bit invoking overlays of more than one page each time one of the pages in a chain is to be overlayed, and a tag bit setting aside selected page buffer store pages from the overlay process, in effect fixing these pages in the accelerator memory.
While there are many ways of physically implementing these functions the most convenient is to utilize a mapping RAM for this purpose. To accomplish these functions the address request is first filtered to isolate the page number bits out of an address containing both page and word coordinates. The page number is encoded in terms of the main memory coordinates and therefore serves as an address to a corresponding field in the RAM which contains the corresponding page address in the page buffer store if that page is already overlayed. In addition to this field each page number address also invokes a link field pointing to, (or indicating) all other related pages.
By this arrangement the link pointers may be dynamically altered according to the application or program executed. Furthermore, by expanding the size of the link field various levels of cross correlation with other pages can be accommodated. By this technique overlays or page swapping in statistically optimal sets can be achieved.